package src.dynamic_programming;

import java.util.Arrays;

/**
 * @author starsea
 * @date 2024-07-30 22:15
 */

public class path {
    //62.不同的路径
    public int uniquePaths(int m, int n) {
        //创建dp
        int[][]dp=new int[m+1][n+1];
        dp[0][1]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];
    }
    //63.不同路径2
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        //创建按dp
        int[][] dp=new int[m+1][m+1];
        dp[0][1]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
               if(obstacleGrid[i-1][j-1]==0)
                {
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }
    //166.珠宝最高价值
    public static void main(String[] args) {
        int[][] arr={{2,1,3},{6,5,4},{7,8,9}};
        int c=jewelleryValue(arr);
    }
    public static int jewelleryValue(int[][] frame) {
        int m=frame.length;
        int n=frame[0].length;
        //创建dp表
        int[][] dp=new int[m+1][n+1];
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
            }
        }
        return dp[m][n];
    }
    //931.下降路径最小和
    static Integer max=Integer.MAX_VALUE;
    public static int minFallingPathSum(int[][] matrix) {
        //创建dp
        int n=matrix.length;
        int[][] dp=new int[n+1][n+2];
        int min=max;
        for(int i=1;i<=n;i++)
        {
            dp[i][0]=max;
            dp[i][n+1]=max;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=Math.min(Math.min(dp[i+1][j-1],dp[i+1][j]),dp[i+1][j+1])+matrix[i-1][j-1];
            }

        }
        for(int j=1;j<n+2;j++)
        {
            min=Math.min(min,dp[n][j]);
        }
        return min;

    }
}

